package com.mj.Set.tree;

import java.util.Comparator;

/**
 * @Author: LDeng
 * @Date: 2021-03-08 10:47
 */
public class RBTree<E> extends BalanceBinarySearchTree<E> {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public RBTree() {
        this(null);
    }

    public RBTree(Comparator<E> comparator) {
        super(comparator);
    }


    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent=node.parent;
        //如果添加的是根节点, 或者上溢到根节点（递归退出条件）
        if(parent==null){
            black(node);
            return;
        }
        //如果父节点是黑色，直接返回
        if(isBlack(parent)) return;
        Node<E> uncle=parent.sibling();
        Node<E> grand=parent.parent;
        //叔父节点是红色
        if(isRed(uncle)){
            black(parent);
            black(uncle);
            Node<E> grand_red= red(grand);//祖父节点染成红色，上溢并递归
            afterAdd(grand_red);
            return;
        }
        //叔父节点不是红色
        if(parent.isLeftChind()){//L
            red(grand);
            if(node.isLeftChind()){//LL
                black(parent);
            }else{//LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{//R
            red(grand);
            if(node.isLeftChind()){//RL
                black(node);
                rotateRight(parent);
            }else{//RR
                black(parent);
            }
            rotateLeft(grand);
        }

    }
    @Override
    protected void afterRemove(Node<E> node,Node<E> replacement) {
        //如果删除的是红色节点， 直接删除即可
        if(isRed(node)) return;

        //用以取代删除节点的节点是红色
        if(isRed(replacement)){
            black(replacement);
            return;
        }
        Node<E> parent= node.parent;
        //删除的叶子节点是根节点， 直接返回
        if(parent==null) return;
        //能来到这里表示删除的是黑色叶子节点
        //Node<E> sibling=node.sibling();
        //判断被删除的节点是左边还是右边(用parent.left是否是空来判断)
        //如果parent.left是空， 则删除的节点在左边，那么sibling在必然在右边， 反之 sibling在左边
        //递归的情况，跟parent的连线还在，所有可以用isLeftChild()来判断
        boolean left=parent.left==null||node.isLeftChind();
        Node<E> sibling=left?parent.right:parent.left;
        if(left){//被删除的节点在左边，兄弟节点在右边
            if(isRed(sibling)){//兄弟节点是红色=>转化成兄弟节点是黑色，复用
                black(sibling);
                red(parent);
                rotateLeft(parent);
                //更换兄弟
                sibling=parent.right;//sibling指向parent.left（黑色）
            }
            //现在可以统一处理sibling是黑色的情况
            if(isBlack(sibling.left)&&isBlack(sibling.right)){//黑黑，没有红色子节点可以借出
                //判断父节点颜色
                boolean parentBlack=isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){
                    afterRemove(parent,null);
                }
            }else {//VS 黑红+红黑+红红, 兄弟节点至少有一个红色节点可以借出
                //向兄弟节点借元素， 三种情况
                //    红节点在兄弟节点右边 兄弟节点左旋+父节点右旋，
                //    红节点在兄弟节点左边             父节点右旋
                //    红节点两边走有，                 父节点右旋
                //这里先把第一种特殊处理一下， 然后统一代码左父节点右旋
                if (isBlack(sibling.right)) {//红节点在右边，先旋转兄弟节点,在将sibling指向父节点的左边
                    rotateRight(sibling);
                    sibling = parent.right;//sibling指向
                }
                //拿到被删除节点父节点的颜色，给兄弟染色
                color(sibling, colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }

        }else{//被删除的节点在右边，兄弟节点在左边（对称处理）
            if(isRed(sibling)){//兄弟节点是红色=>转化成兄弟节点是黑色，复用
                black(sibling);
                red(parent);
                rotateRight(parent);
                //更换兄弟
                sibling=parent.left;//sibling指向parent.left（黑色）
            }
            //现在可以统一处理sibling是黑色的情况
            if(isBlack(sibling.left)&&isBlack(sibling.right)){//黑黑，没有红色子节点可以借出
                //判断父节点颜色
                boolean parentBlack=isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){
                    afterRemove(parent,null);
                }
            }else{//VS 黑红+红黑+红红, 兄弟节点至少有一个红色节点可以借出
                //向兄弟节点借元素， 三种情况
                //    红节点在兄弟节点右边 兄弟节点左旋+父节点右旋，
                //    红节点在兄弟节点左边             父节点右旋
                //    红节点两边走有，                 父节点右旋
                //这里先把第一种特殊处理一下， 然后统一代码左父节点右旋
                if(isBlack(sibling.left)){//红节点在右边，先旋转兄弟节点,在将sibling指向父节点的左边
                    rotateLeft(sibling);
                    sibling=parent.left;//sibling指向
                }
                //拿到被删除节点父节点的颜色，给兄弟染色
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }


    //节点染色并返回染色后的节点
    private Node<E> color(Node<E> node, boolean color) {
        if (node == null) return node;
        ((RBNode<E>) node).color = color;
        return node;
    }

    //将节点染成红色并返回
    private Node<E> red(Node<E> node){
        return color(node,RED);
    }

    //将节点染成黑色并返回
    private Node<E> black(Node<E> node){
        return color(node,BLACK);
    }

    //取出当前节点颜色
    private boolean colorOf(Node<E> node){
        //空节点返回黑色，其他根据实际是什么颜色就返回什么颜色
        return node==null?BLACK:((RBNode<E>) node).color;
    }

    //判断节点是否为黑色
    private boolean isBlack(Node<E> node){
        return colorOf(node)==BLACK;
    }
    //判断节点是否为红色
    private boolean isRed(Node<E> node){
        return colorOf(node)==RED;
    }


    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element,parent);
    }

    private static class RBNode<E> extends Node<E> {
        boolean color=RED;

        public RBNode(E element, Node<E> parent) {
            super(element, parent);
        }

        @Override
        public String toString() {
            String str="";
            if(color==RED){
                str="R_";
            }
            return str+element.toString();
        }
    }


}
